/**
 * 253. 会议室 II
 * https://leetcode-cn.com/problems/meeting-rooms-ii/
 */

/**
 * @param {*} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[]} heap
 */
function resolveHeap(heap) {
  for (let i = Math.floor(heap.length / 2 - 1); i >= 0; i -= 1) {
    const value = heap[i];
    const left = i * 2 + 1;
    const right = left + 1;
    const leftValue = heap[left];
    const rightValue = heap[right] || Infinity;
    if (value <= leftValue && value <= rightValue) {
      continue;
    }
    if (leftValue <= rightValue) {
      swap(heap, i, left);
    } else {
      swap(heap, i, right);
    }
  }
}

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = [];
  for (let i = 0; i < intervals.length; i += 1) {
    const [start, end] = intervals[i];
    if (heap.length === 0 || heap[0] > start) {
      heap.push(end);
    } else {
      heap[0] = end;
      swap(heap, 0, heap.length - 1);
    }
    resolveHeap(heap);
  }
  return heap.length;
}

console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]]) === 2);
console.log(minMeetingRooms([[7, 10], [2, 4]]) === 1);
